package 图.dfs;

import java.util.ArrayList;
import java.util.Scanner;

public class map {
    public static ArrayList<String> vertexList;
    public int[][] edges;
    public boolean[] isVisited;
    public map(int n){
         edges = new int[n][n];
        vertexList = new ArrayList<String>(n);
        int numberEdges = 0;
        isVisited = new boolean[n];
    }

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        System.out.println("请输入图中的每一个元素");
        String Vertexes[] = sc.nextLine().split(" ");
        map map = new map(Vertexes.length);
        for (String vertex : Vertexes){
            vertexList.add(vertex);
        }
        System.out.println(Vertexes.length);
        map.creatMap(Vertexes.length);
        map.dfs(map.isVisited, 0);



    }

    public void dfs(boolean[] isVisited, int i){
        for (; i < vertexList.size(); i++) {
            if (!isVisited[i]){
                //先访问一个节点并输出
                if (i < vertexList.size() - 1){
                    System.out.print(vertexList.get(i) + "->");
                }
                else {
                    System.out.println(vertexList.get(i));
                }
                //将该节点设置为已访问
                isVisited[i] = true;
                //茶找该节点的第一个邻节点w
                int w = getFirstNeighbor(i);
                while (w != -1){
                    if (!isVisited[w]){
                        dfs(isVisited , w);
                    }
                    w = getNextNeighbor(i,w);

                }
            }
        }

    }
    public void creatMap(int n){
        Scanner sc=new Scanner(System.in);
        int[][] connection = new int[n][3];
        System.out.println("请输入元素间的关系");
        for (int i = 0; i < connection.length; i++) {
            for (int j = 0; j < connection[i].length ; j++) {
                connection[i][j]=sc.nextInt();
            }
        }

        for (int i = 0; i < connection.length; i++) {
            int v1 = connection[i][0];
            int v2 = connection[i][1];
            edges[v1][v2] = connection[i][2];
        }
        System.out.println("图中各个元素的关系矩阵如下");
        for (int i = 0; i < edges.length; i++) {
            for (int j = 0; j < edges[i].length ; j++) {
                System.out.print(edges[i][j]);
            }
            System.out.println();
        }
    }
    public int getFirstNeighbor(int index){
        for (int i = 0; i < vertexList.size(); i++) {
            if (edges[index][i]>0){
                return i;
            }
        }
        return -1;
    }
    public int getNextNeighbor(int v1,int v2){
        for (int j = v2 + 1; j < vertexList.size(); j++) {
            if (edges[v1][j] > 0){
                return j;
            }
        }
        return -1;
    }
}

